Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]
Example 2:
Input: root = [1], target = 0.000000, k = 1 Output: [1]
Constraints:
- The number of nodes in the tree is
n. 1 <= k <= n <= 104.0 <= Node.val <= 109-109 <= target <= 109
Follow up: Assume that the BST is balanced. Could you solve it in less than O(n) runtime (where n = total nodes)?
getPredecessor(N), which returns the next smaller node to N.getSuccessor(N), which returns the next larger node to N.
Average Rating: 4.20 (25 votes)
Solution
Overview
The problem is a BST variation of the "kth-smallest" classical problem. It is popular both in Google and Facebook, but these two companies are waiting for you to show different approaches to this problem. We're proposing 3 solutions here, and it's more an overview.
Prerequisites
Because of that, you might want first to check out the list of prerequisites:
-
Inorder traversal of BST is an array sorted in the ascending order. To compute inorder traversal follow the direction
Left -> Node -> Right.
Google vs. Facebook
There are three ways to solve the problem:
-
Approach 1. Sort, O(NlogN) time. The idea is to convert BST into an array, sort it by the distance to the target, and return the k closest elements.
-
Approach 2. Facebook-friendly, heap, O(Nlogk) time. We could use the heap of capacity k, sorted by the distance to the target. It's not an optimal but very straightforward solution - traverse the tree, push the elements into the heap, and then return this heap. Facebook interviewer would insist on implementing this solution because the interviews are a bit shorter than Google ones, and it's important to get problem solved end-to-end.
-
Approach 3. Google-friendly, quickselect, O(N) time. Here you could find a very detailed explanation of quickselect algorithm. In this article, we're going to provide a relatively brief implementation. Google guys usually prefer the best-time solutions, well-structured clean skeleton, even if you have no time to implement everything in time end-to-end.
Approach 1: Recursive Inorder + Sort, O(N log N) time
Intuition

The most straightforward approach is to build inorder traversal and then find the k closest elements using build-in sort.
Algorithm
-
Build an inorder traversal array.
-
Find the k closest to the target elements using build-in sort.
Implementation
Complexity Analysis
-
Time complexity: O(NlogN). O(N) to build inorder traversal and then O(NlogN) to sort it.
-
Space complexity: O(N) to store list
numsof N elements.
Approach 2: Recursive Inorder + Heap, O(N log k) time

Algorithm
-
Instantiate the heap with "less close element first" strategy so that the heap contains the elements that are closest to the target.
-
Use inorder traversal to traverse the tree following the direction
Left -> Node -> Right.- Push all elements into heap during the traversal, keeping the heap size less than or equal to k.
-
As a result, the heap contains k elements that are closest to target. Convert it into a list and return.
Implementation
Optimisations
One could optimize the solution by adding the stop condition. Inorder traversal pops the elements in the sorted order. Hence once the distance of the current element to the target becomes greater than the distance of the first element in a heap, one could stop the computations. The overall worst-case time complexity would be still O(Nlogk), but the average time could be improved to O(Hlogk), where H is a tree height.
Complexity Analysis
-
Time complexity: O(Nlogk) to push N elements into the heap of the size k.
-
Space complexity: O(k+H) to keep the heap of k elements and the recursion stack of the tree height.
Approach 3: QuickSelect, O(N) time.
Hoare's selection algorithm
Quickselect is a textbook algorithm
typically used to solve the problems "find kth something":
kth smallest, kth largest, etc. Like quicksort, quickselect was developed
by Tony Hoare,
and also known as Hoare's selection algorithm.
It has O(N) average time complexity and widely used in practice. It is worth to note that its worst-case time complexity is O(N2), although the probability of this worst-case is negligible.
The approach is the same as for quicksort.
One chooses a pivot and defines its position in a sorted array in a linear time using the so-called partition algorithm.
As an output, we have an array where the pivot is on its perfect position in the ascending sorted array, sorted by the frequency. All elements on the left of the pivot are more close to the target than the pivot, and all elements on the right are less close or on the same distance from the target.
The array is now split into two parts.
If by chance, our pivot element took kth final position,
then k elements on the left are these k
closest elements we're looking for.
If not, we can choose one more pivot and
place it in its perfect position.

If that were a quicksort algorithm, one would have to process
both parts of the array. That would result in O(NlogN) time complexity.
In this case, there is no need to deal with both parts since one knows
in which part to search for kth closest element, and that
reduces the average time complexity to O(N).
Algorithm
The algorithm is relatively straightforward:
-
Traverse the tree and convert it into array
nums. -
Implement the simple function to compute the distance to the target. Note that the distance is not unique. That means we need a partition algorithm that works fine with duplicates.
-
Work with
numsarray. Use a partition scheme (please check the next section) to place the pivot into its perfect positionpivot_indexin the sorted array, move more close elements to the left of the pivot, and less close or of the same distance - to the right. -
Compare
pivot_indexandk.-
If
pivot_index == k, the pivot is thekth less close element, and all elements on the left are the k closest elements to the target. Return these elements. -
Otherwise, choose the side of the array to proceed recursively.
-
Hoare's Partition vs. Lomuto's Partition
There is a zoo of partition algorithms. The most simple one is Lomuto's Partition Scheme.
The drawback of Lomuto's partition is that it fails with duplicates.
Here we work with an array of unique elements, but they are compared by the distances to the target, which are not unique. That's why we choose Hoare's Partition here.
Hoare's partition is more efficient than Lomuto's partition because it does three times fewer swaps on average, and creates efficient partitions even when all values are equal.
Here is how it works:
-
Move pivot at the end of the array using swap.
-
Set the pointer at the beginning of the array
store_index = left. -
Iterate over the array and move all more close elements to the left
swap(store_index, i). Movestore_indexone step to the right after each swap. -
Move the pivot to its final place, and return this index.
Implementation
Complexity Analysis
-
Time complexity: O(N), O(N2) in the worst case. Please refer to this card for the good detailed explanation of Master Theorem. Master Theorem helps to get an average complexity by writing the algorithm cost as T(N)=aT(N/b)+f(N). Here we have an example of Master Theorem case III: T(N)=T(2N)+N, that results in O(N) time complexity. That's the case of random pivots.
In the worst-case of constantly bad chosen pivots, the problem is not divided by half at each step, it becomes just one element less, that leads to O(N2) time complexity. It happens, for example, if at each step you choose the pivot not randomly, but take the rightmost element. For the random pivot choice, the probability of having such a worst-case is negligibly small.
-
Space complexity: O(N) to store
nums.
How about the following solution? It visits all the nodes at most twice.
- Store all values into an array. If you do an inorder traversal the values should be sorted.
- Iterate through this array and find the single closest value to the target.
- Now you can have two pointers that begin from that closest value and expands to the left and right.
- You determine which way you expand by simply comparing the values of the left and right pointer.
- If the left value is closer to the target then expand the left pointer by 1 and otherwise expand the right pointer by 1
var closestKValues = function(root, target, k) {
// Simple inorder traversal to gather nodes
let inorder= [];
inorderSearch(root,inorder);
if(inorder.length == 0)
return;
// grab difference of first first/smallest value
let currDifference = Math.abs(target-inorder[0])
let result = [];
// start at index 1
for(let i = 1; i < inorder.length; i++) {
let prevDifference = currDifference;
currDifference = Math.abs(target-inorder[i]);
// basically says if you notice that you've arrived at the closest value to the target
if(currDifference > prevDifference || i == inorder.length-1) {
let left = null, right = null;
if(Math.abs(inorder[i-1]-target) < Math.abs(inorder[i]-target) ) {
left = i-1, right = i-1;
} else {
left = i, right = i;
}
// push the one single value that's closest to the target
result.push(inorder[right]);
// start expanding left and right until the total is k
while(right-left+1 < k && (right < inorder.length-1 || left > 0) ) {
let rv = inorder[right+1];
let lv = inorder[left-1];
if(right < inorder.length-1 && left > 0) {
let ld = Math.abs(target-lv), rd = Math.abs(target-rv);
if(ld < rd) {
result.push(lv);
left--;
} else {
result.push(rv);
right++;
}
} else if(right < inorder.length-1) {
result.push(rv);
right++;
} else {
result.push(lv);
left--;
}
}
// you only need to run this while loop once so break once you're done
break;
}
}
return result.length == 0 ? inorder : result;
};
function inorderSearch(root, inorder) {
if(root == null)
return;
inorderSearch(root.left, inorder);
inorder.push(root.val);
inorderSearch(root.right, inorder);
}
It could be done in O(N) Time and O(K) Space with inorder and using a deque.
It's just like a sliding window.
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
Deque<Integer> deque = new LinkedList<>();
inorder(deque, root, target, k);
return new ArrayList(deque);
}
private void inorder(Deque<Integer> deque, TreeNode node, double target, int k) {
if (node == null)
return;
inorder(deque, node.left, target, k);
double val = Double.valueOf(node.val);
if (deque.size() == k) {
if (Math.abs(Double.valueOf(deque.peekFirst())-target) > Math.abs(val - target)) {
deque.pollFirst();
deque.addLast(node.val);
} else return;
} else {
deque.addLast(node.val);
}
inorder(deque, node.right, target, k);
}
}September 29, 2020 11:03 AM
@andvary Great solution and analysis. I assume Facebook looks for most optimized solution as well. Would it help to implement Quick select for facebook interview?
why inorder traversal takes O(nlogn)? Isn't it just O(n)?
I'll never understand some of these difficulty level settings. This is basically a traversal with a max heap added in, not really a "hard". In other places, they have some DPs as "easy" which seems crazy.
If I'm not mistaken, the QuickSelect solution uses Lomuto partition rather than Hoare's, whereas it claims to use the latter.
December 21, 2020 6:09 AM
I think first two approaches are sub-optimal sorting already sorted data set.
February 2, 2021 12:18 PM
This is the best answer for this question: https://leetcode.com/problems/closest-binary-search-tree-value-ii/discuss/70511/AC-clean-Java-solution-using-two-stacks/72757
I think there is a very simple O(N) solution. No any extra advanced data structure. Just two pointers.
class Solution:
def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
L = []
def inorder(n):
if n:
inorder(n.left)
L.append(n.val)
inorder(n.right)
inorder(root)
D, p = [], None
for i, n in enumerate(L):
D.append(abs(n - target))
if p is None or D[p] > D[-1]:
p = i
l, r = p, p
while r - l + 1 < k:
if l == 0:
r += 1
elif r == len(D) - 1:
l -= 1
elif D[r+1] > D[l-1]:
l -= 1
else:
r += 1
return L[l:r+1]
The article is well-written for the listed solutions, but misleading for not covering other more optimal options.
Given it's about finding a target in BST, binary search is the most obvious route and guarantees the performance. The only tricky part is to expand from the closest node to the closest K nodes, which has some trade-offs to consider :
- Speed over space: in order to quickly expand from closest 1 to K, using an aux array is the way to go
Time O(N), Space O(N); this approach is fairly straightforward to implement. - Space over speed: binary search to find the closest node, and use the predecessor and successor pattern to expand to the next nodes (using a parent pointer, both could be done in
O(logN)on average).Time O(KlogN), Space O(1), since only a few pointers are needed besides the result. Note this is still a lot better thanO(NlogK)of the Inorder + Heap approach, but a bit lengthy to implement.
Imo the above layer qualifies this problem as a "hard", and just because test cases all passed with all sub-optimal solutions doesn't change the difficulty level of the problem itself.
You don't have any submissions yet.
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: vector<int> closestKValues(TreeNode* root, double target, int k) { }};